#include <algorithm>
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>>ans;
        if(nums.size()<3)return ans;
        sort(nums.begin(),nums.end());
        //nums.erase(unique(nums.begin(),nums.end()),nums.end());
        if(nums[0]>0)return ans;
        
        for(int i=0;i<nums.size()-2;i++)
        {
            if(i&&nums[i-1]==nums[i])continue;
            int l=i+1,r=nums.size()-1;
            for(;l<r;l++)
            {
                if(l>i+1&&nums[l]==nums[l-1])continue;
                while(nums[i+nums[l]+nums[r]]>0)r--;
                if(nums[i]+nums[l]+nums[r]==0&&l<r)ans.push_back({nums[i],nums[l],nums[r]});
            }
        }
        return ans;
    }
};